home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung / Power-Programmierung (Tewi)(1994).iso / magazine / drdobbs / 1987 / 08 / bowman.exp < prev    next >
Text File  |  1987-08-12  |  2KB  |  101 lines
  1.  
  2.       1: bktkfind( node )
  3.       2: begin
  4.       3: if( node = SUCCESS )
  5.       4: then
  6.       5:     return( I_FOUND_IT )
  7.       6: endif
  8.       7: for( each_choice_at_this_node )
  9.       8: do
  10.       9:     ret_stat = bktkfind( child_node )
  11.      10:     if( ret_stat = SUCCESS )
  12.      11:     then
  13.      12:         return( ret_stat )
  14.      13:     endif
  15.      14: done
  16.      15: return( FAIL )
  17.      16: endproc
  18.  
  19. Example 1:  Pseudocode for a chronological backtracking function
  20.  
  21.  
  22.  
  23.       @puzzle
  24.       ----
  25.       $-$-    (`$' = Blank)
  26.       ----
  27.       -$$-
  28.       @words
  29.       best
  30.       tamp
  31.       tops
  32.       era
  33.       to
  34.  
  35. Example 2: Sample input
  36.  
  37.  
  38.  
  39.  
  40.       best
  41.       $r$o   (`$' = Blank)
  42.       tamp
  43.       o$$s
  44.  
  45. Example 3: Sample output
  46.  
  47.  
  48.  
  49.  
  50.         1: posn := [];
  51.         2: (forall j in [ 1..8 ])
  52.         3:  { j : j in [ 1..8 ] | OK }
  53.         4:  unattacked := { 1..8 } - { posn(k) + (j-k)*slope
  54.         5:         : k in [ 1..j-1 ],
  55.         6:         slope in [ -1..+1 ] }
  56.         7:  if( unattacked = {} )
  57.         8:  then
  58.         9:    FAIL;
  59.        10:  else
  60.        11:    posn(j) := ord unattacked;
  61.        12:  endif;
  62.        13: end forall;
  63.        14: print( posn );
  64.  
  65. Example 4: Eight queens problem
  66.  
  67.  
  68.  
  69.  
  70.  
  71.      1: solve( length, width )
  72.      2: int  length, width;
  73.      3: {
  74.      4:   int  l, w, i, len, tmp, type;
  75.      5:   char old[ WORDLEN - MINWORD + 1 ];
  76.      6:
  77.      7:   w = width;
  78.      8:   l = length;
  79.      9:   len = next( &l, &w, &type );
  80.     10:   if( len == 0 )
  81.     11:     return( SOLVED );
  82.     12:
  83.     13:   for(i = 0;i<MAXWORD&&WORD(len,i)[0]!=NIL;i++){
  84.     14:     if( FLAG(len, i) == FREE
  85.     15:     && itfits(l, w, WORD(len, i), type) ){
  86.     16:       FLAG(len, i) = USED;
  87.     17:       enter(old, l, w, WORD(len,i), type);
  88.     18:       prev = type;
  89.     19:       tmp = solve( l, w );
  90.     20:       if( tmp == SOLVED )
  91.     21:         return( SOLVED );
  92.     22:       restore( old, l, w, type );
  93.     23:       FLAG(len, i) = FREE;
  94.     24:     }
  95.     25:   }
  96.     26:
  97.     27:   return( 0 );
  98.     28: }
  99.  
  100. Example 5: The function solve().
  101.